package codingforgreat.class47;
// 同时支持范围增加 + 范围修改 + 范围查询的动态开点线段树（累加和）
// 真的用到！才去建立
// 懒更新，及其所有的东西，和普通线段树，没有任何区别！
public class Code02_DynamicSegmentTree {
    public static class Node{
        int sum;
        int lazy;
        int change;
        boolean update;
        Node left;
        Node right;
    }
    public static class SegmentTree{
        Node root;
        int size;
        public SegmentTree(int max){
            root = new Node();
            size = max;
        }
        public void update(int s, int e, int v) {
            update(root, 1, size, s, e, v);
        }

        private void update(Node root, int l, int r, int s, int e, int v) {
            if(s <= l && e >= r){
                root.sum = (r - l + 1) * v;
                root.lazy = 0;
                root.update = true;
                root.change = v;
            }else{
                int mid = (l + r) /2;
                pushDown(root,mid - l + 1, r - mid);
                if(s <= mid){
                    update(root.left,l,mid,s,e,v);
                }
                if(e > mid){
                    update(root.right,mid + 1,r,s,e,v);
                }
                pushUp(root);
            }
        }
        public void add(int s, int e, int v) {
            add(root, 1, size, s, e, v);
        }
        private void add(Node root, int l, int r, int s, int e, int v) {
            if(s <= l && e >= r){
                root.sum += v * (r - l + 1);
                root.lazy += v;
            }else{
                int mid = (l + r) /2;
                pushDown(root,mid - l + 1, r - mid);
                if(s <= mid){
                    add(root.left,l,mid,s,e,v);
                }
                if(e > mid){
                    add(root.right,mid + 1,r,s,e,v);
                }
                pushUp(root);
            }
        }
        public int query(int s, int e) {
            return query(root, 1, size, s, e);
        }

        private int query(Node root, int l, int r, int s, int e) {
           if(s <= l && e >= r){
               return root == null ? 0 : root.sum;
           }
           int mid = (l + r) / 2;
            pushDown(root, mid - l + 1, r - mid);
            int ans = 0;
            if (s <= mid) {
              ans +=  query(root.left, l, mid, s, e);
            }
            if (e > mid) {
               ans += query(root.right, mid + 1, r, s, e);
            }
            return ans;
        }

        public void pushUp(Node node){
            node.sum = 0;
            if(node.left != null){
                node.sum += node.left.sum;
            }
            if(node.right != null){
                node.sum += node.right.sum;
            }
        }
        public void pushDown(Node node,int ln,int rn){
            if(node.left == null){
                node.left = new Node();
            }
            if(node.right == null){
                node.right = new Node();
            }
            if(node.update){
                node.left.update = true;
                node.right.update = true;
                node.left.sum = node.change * ln;
                node.right.sum = node.change * rn;
                node.left.lazy = 0;
                node.right.lazy = 0;
                node.left.change = node.change;
                node.right.change = node.change;
                node.update = false;
            }
            if(node.lazy != 0){
                node.left.lazy += node.lazy;
                node.right.lazy += node.lazy;
                node.left.sum += node.lazy * ln;
                node.right.sum += node.lazy * rn;
                node.lazy = 0;
            }
        }
    }


    public static class Right {
        public int[] arr;

        public Right(int size) {
            arr = new int[size + 1];
        }

        public void add(int s, int e, int v) {
            for (int i = s; i <= e; i++) {
                arr[i] += v;
            }
        }

        public void update(int s, int e, int v) {
            for (int i = s; i <= e; i++) {
                arr[i] = v;
            }
        }

        public int query(int s, int e) {
            int sum = 0;
            for (int i = s; i <= e; i++) {
                sum += arr[i];
            }
            return sum;
        }

    }

    public static void main(String[] args) {
        int n = 1000;
        int value = 50;
        int createTimes = 5000;
        int operateTimes = 5000;
        System.out.println("测试开始");
        for (int i = 0; i < createTimes; i++) {
            int size = (int) (Math.random() * n) + 1;
            SegmentTree dst = new SegmentTree(size);
            Right right = new Right(size);
            for (int k = 0; k < operateTimes; k++) {
                double choose = Math.random();
                if (choose < 0.333) {
                    int a = (int) (Math.random() * size) + 1;
                    int b = (int) (Math.random() * size) + 1;
                    int s = Math.min(a, b);
                    int e = Math.max(a, b);
                    int v = (int) (Math.random() * value);
                    dst.update(s, e, v);
                    right.update(s, e, v);
                } else if (choose < 0.666) {
                    int a = (int) (Math.random() * size) + 1;
                    int b = (int) (Math.random() * size) + 1;
                    int s = Math.min(a, b);
                    int e = Math.max(a, b);
                    int v = (int) (Math.random() * value);
                    dst.add(s, e, v);
                    right.add(s, e, v);
                } else {
                    int a = (int) (Math.random() * size) + 1;
                    int b = (int) (Math.random() * size) + 1;
                    int s = Math.min(a, b);
                    int e = Math.max(a, b);
                    int ans1 = dst.query(s, e);
                    int ans2 = right.query(s, e);
                    if (ans1 != ans2) {
                        System.out.println("出错了!");
                        System.out.println(ans1);
                        System.out.println(ans2);
                    }
                }
            }
        }
        System.out.println("测试结束");
    }
}
